class Solution {
public:
	int GetValue(const string& s, int begin, int end) {
		int value = 0;
		if (s[begin] == '0' && end > begin) {
			return -1;
		}
		for (int i = begin; i <= end; ++i) {
			value = value * 10 + (s[i] - '0');
		}
		return value;
	}

    vector<string> restoreIpAddresses(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		int A[4];
		vector<string> result;

		for (int i = 0; i < 3 && i < s.length(); ++i) {
			A[0] = GetValue(s, 0, i);
			if (!(A[0] >= 0 && A[0] < 256)) {
				continue;
			}
			for (int j = i + 1; j < i + 4 && j < s.length(); ++j) {
				A[1] = GetValue(s, i + 1, j);
				if (!(A[1] >= 0 && A[1] < 256)) {
					continue;
				}
				for (int k = j + 1; k < j + 4 && k < s.length(); ++k) {
					A[2] = GetValue(s, j + 1, k);
					if (!(A[2] >= 0 && A[2] < 256)) {
						continue;
					}
					if (k + 1 >= s.length() || s.length() - k - 1 > 3) {
						continue;
					}
					A[3] = GetValue(s, k + 1, s.length() - 1);
					if (!(A[3] >= 0 && A[3] < 256)) {
						continue;
					}
					string solution;
					solution += s.substr(0, i + 1);
					solution += '.';
					solution += s.substr(i + 1, j - i);
					solution += '.';
					solution += s.substr(j + 1, k - j);
					solution += '.';
					solution += s.substr(k + 1, s.length() - k - 1);
					result.push_back(solution);
				}
			}
		}
		return result;
    }
};